package exercises;

public class Sorting {
	public static int[] MergeSort(int[] elements)
	{
		if(elements.length<=1)
			return elements;
		
		int middle = elements.length / 2;
		int[] leftElements = new int[middle];
		int[] rightElements = new int[elements.length - middle];
		
		for(int i=0;i<elements.length;i++){
			if(i<middle)
				leftElements[i] = elements[i];
			else 
				rightElements[i-middle] = elements[i];
		}
		
		int[] sortedLeft = MergeSort(leftElements);
		int[] sortedRight = MergeSort(rightElements);
		
		return Combine(sortedLeft, sortedRight);
	}
	
	private static int[] Combine(int[] left, int[] right){
		int[] combined = new int[left.length + right.length];
		int j = 0;
		int i = 0;
		
		while(i<left.length && j<right.length){
			if(left[i] < right[j]){
				combined[i+j] = left[i];
				i++;
			}
			else {
				combined[i+j] = right[j];
				j++;
			}
		}
				
		if(i<left.length)
			for(int it=i; it<left.length; it++)
				combined[it+j] = left[it];
		else if (j<right.length)
			for(int it=j; it<right.length; it++)
				combined[it+i] = right[it];
		return combined;
	}
}
